計算量O(n)の革命的なソートアルゴリズムをPHPでも

<?php

namespace stalin;

function sort(array $xs): array
{
    if (count($xs) <= 1) {
        return $xs;
    }
    
    $zs = $xs;
    $x = array_shift($zs);
    $y = array_shift($zs);
    
    if ($x <= $y) {
        return [$x, ...sort([$y, ...$zs])];
    }
    
    return sort([$x, ...$zs]);
}

echo json_encode(\stalin\sort([1, 2, 1, 1, 4, 3, 9]));
// [1,2,4,9]